package leetcode.code1559;

public class Solution {

	class Union {

		int[] r;
		int[] s;

		public Union(int m, int n) {
			r = new int[m * n];
			s = new int[m * n];
			for (int i = 0; i < r.length; i++) {
				r[i] = i;
				s[i] = 1;
			}
		}

		public void union(int cur, int up) {
			int rc = this.find(cur);
			int ru = this.find(up);
			this.r[rc] = ru;
			this.s[ru] += this.s[rc];
		}

		public boolean isSameSet(int left, int up) {
			return this.find(left) == this.find(up);
		}

		public int size(int left) {
			return this.s[this.find(left)];
		}

		private int find(int left) {
			if (this.r[left] != left) {
				this.r[left] = this.find(this.r[left]);
			}
			return this.r[left];
		}

	}

	public boolean containsCycle(char[][] grid) {
		int m = grid.length, n = grid[0].length;
		Union un = new Union(m, n);
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				char c = grid[i][j];
				int cur = this.index(i, j, n);
				int left = this.index(i, j - 1, n);
				int up = this.index(i - 1, j, n);
				if (i > 0 && j > 0 && c == grid[i - 1][j] && c == grid[i][j - 1] && un.isSameSet(left, up)
						&& un.size(left) >= 3) {
					return true;
				}
				if (i > 0 && c == grid[i - 1][j]) {
					un.union(cur, up);
				}
				if (j > 0 && c == grid[i][j - 1]) {
					un.union(cur, left);
				}
			}
		}
		return false;
	}

	private int index(int x, int y, int n) {
		return x * n + y;
	}

}
